package com.dyz.leetcode._20_dynamicProgramming._279;

import java.util.Arrays;

public class numSquares01 {
    // 完全平方数最小为 1，最大为 sqrt(n)
    // 也就是我们要从 nums = [1, 2, ..., sqrt(n)] 数组里选出几个数，
    // 令其平方和为 n(背包容量)。求最少的完全平方数
    public int numSquares(int n) {

        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <=Math.sqrt(n) ; i++) {
            for (int j = i*i; j <=n ; j++) {
                dp[j] = Math.min(dp[j], dp[j-i*i]+1);

            }

        }
        return dp[n];

    }
}
